YES 48.722
H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:
↳ HASKELL
↳ LR
mainModule Main
| ((lines :: [Char] -> [[Char]]) :: [Char] -> [[Char]]) |
module Main where
Lambda Reductions:
The following Lambda expression
\(l,_)→l
is transformed to
The following Lambda expression
\(_,s')→s'
is transformed to
The following Lambda expression
\(_,zs)→zs
is transformed to
The following Lambda expression
\(ys,_)→ys
is transformed to
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
mainModule Main
| ((lines :: [Char] -> [[Char]]) :: [Char] -> [[Char]]) |
module Main where
Case Reductions:
The following Case expression
case | s' of |
| [] | → [] |
| _ : s'' | → lines s'' |
is transformed to
lines0 | [] | = [] |
lines0 | (_ : s'') | = lines s'' |
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
mainModule Main
| ((lines :: [Char] -> [[Char]]) :: [Char] -> [[Char]]) |
module Main where
Replaced joker patterns by fresh variables and removed binding patterns.
Binding Reductions:
The bind variable of the following binding Pattern
xs@(vz : wu)
is replaced by the following term
vz : wu
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
mainModule Main
| ((lines :: [Char] -> [[Char]]) :: [Char] -> [[Char]]) |
module Main where
Cond Reductions:
The following Function with conditions
is transformed to
undefined0 | True | = undefined |
undefined1 | | = undefined0 False |
The following Function with conditions
span | p [] | = ([],[]) |
span | p (vz : wu) | |
is transformed to
span | p [] | = span3 p [] |
span | p (vz : wu) | = span2 p (vz : wu) |
span2 | p (vz : wu) | =
span1 p vz wu (p vz) |
where |
span0 | p vz wu True | = ([],vz : wu) |
|
|
span1 | p vz wu True | = (vz : ys,zs) |
span1 | p vz wu False | = span0 p vz wu otherwise |
|
| |
| |
| |
| |
| |
|
span3 | p [] | = ([],[]) |
span3 | xu xv | = span2 xu xv |
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
mainModule Main
| ((lines :: [Char] -> [[Char]]) :: [Char] -> [[Char]]) |
module Main where
Let/Where Reductions:
The bindings of the following Let/Where expression
let | |
| |
|
lines0 | [] | = [] |
lines0 | (vw : s'') | = lines s'' |
|
| |
| |
|
vu44 | | = break ('\10' ==) s |
|
in | l : lines0 s' |
are unpacked to the following functions on top level
linesL | xw | = linesL0 xw (linesVu44 xw) |
linesVu44 | xw | = break ('\10' ==) xw |
linesS' | xw | = linesS'0 xw (linesVu44 xw) |
linesLines0 | xw [] | = [] |
linesLines0 | xw (vw : s'') | = lines s'' |
The bindings of the following Let/Where expression
span1 p vz wu (p vz) |
where |
span0 | p vz wu True | = ([],vz : wu) |
|
|
span1 | p vz wu True | = (vz : ys,zs) |
span1 | p vz wu False | = span0 p vz wu otherwise |
|
| |
| |
| |
| |
| |
are unpacked to the following functions on top level
span2Span1 | xx xy p vz wu True | = (vz : span2Ys xx xy,span2Zs xx xy) |
span2Span1 | xx xy p vz wu False | = span2Span0 xx xy p vz wu otherwise |
span2Span0 | xx xy p vz wu True | = ([],vz : wu) |
span2Ys0 | xx xy (ys,wv) | = ys |
span2Vu43 | xx xy | = span xx xy |
span2Ys | xx xy | = span2Ys0 xx xy (span2Vu43 xx xy) |
span2Zs0 | xx xy (ww,zs) | = zs |
span2Zs | xx xy | = span2Zs0 xx xy (span2Vu43 xx xy) |
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
mainModule Main
| ((lines :: [Char] -> [[Char]]) :: [Char] -> [[Char]]) |
module Main where
Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
mainModule Main
| (lines :: [Char] -> [[Char]]) |
module Main where
Haskell To QDPs
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_span2Ys00(xz282, xz283, xz284) → new_span2Ys(xz282, xz284)
new_span2Ys0(xz282, xz283, xz284, Succ(xz2850), Zero) → new_span2Ys(xz282, xz284)
new_span2Ys0(xz282, xz283, xz284, Succ(xz2850), Succ(xz2860)) → new_span2Ys0(xz282, xz283, xz284, xz2850, xz2860)
new_span2Ys0(xz282, xz283, xz284, Zero, Succ(xz2860)) → new_span2Ys00(xz282, xz283, xz284)
new_span2Ys(xz7, :(Char(Succ(xz6000)), xz61)) → new_span2Ys0(xz7, xz6000, xz61, xz7, xz6000)
new_span2Ys(xz7, :(Char(Zero), xz61)) → new_span2Ys(xz7, xz61)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_span2Ys0(xz282, xz283, xz284, Zero, Succ(xz2860)) → new_span2Ys00(xz282, xz283, xz284)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3
- new_span2Ys(xz7, :(Char(Succ(xz6000)), xz61)) → new_span2Ys0(xz7, xz6000, xz61, xz7, xz6000)
The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3, 1 >= 4, 2 > 5
- new_span2Ys(xz7, :(Char(Zero), xz61)) → new_span2Ys(xz7, xz61)
The graph contains the following edges 1 >= 1, 2 > 2
- new_span2Ys0(xz282, xz283, xz284, Succ(xz2850), Succ(xz2860)) → new_span2Ys0(xz282, xz283, xz284, xz2850, xz2860)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 5 > 5
- new_span2Ys0(xz282, xz283, xz284, Succ(xz2850), Zero) → new_span2Ys(xz282, xz284)
The graph contains the following edges 1 >= 1, 3 >= 2
- new_span2Ys00(xz282, xz283, xz284) → new_span2Ys(xz282, xz284)
The graph contains the following edges 1 >= 1, 3 >= 2
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_linesL0(xz111, xz112, xz113, Succ(xz1140), Succ(xz1150)) → new_linesL0(xz111, xz112, xz113, xz1140, xz1150)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_linesL0(xz111, xz112, xz113, Succ(xz1140), Succ(xz1150)) → new_linesL0(xz111, xz112, xz113, xz1140, xz1150)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 5 > 5
↳ HASKELL
↳ LR
↳ HASKELL
↳ CR
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
Q DP problem:
The TRS P consists of the following rules:
new_linesLines0(Char(Zero), :(xz100, xz101), xz11) → new_linesLines01(:(xz100, xz101), xz11, xz100, xz101)
new_linesLines08(xz978, xz979, xz980, xz981, xz982) → new_linesLines07(xz978, xz979, xz980, xz981, xz982, new_span2Ys1(xz980, xz982))
new_linesLines013(xz887, xz888, xz889, xz890) → new_linesLines012(xz887, xz888, xz889, xz890, new_span2Ys1(xz888, xz890))
new_linesLines07(xz978, xz979, xz980, xz981, xz982, xz985) → new_linesLines09(xz978, xz979, xz980, xz982)
new_linesLines00(xz119, xz120, xz121, Succ(xz1220), Succ(xz1230)) → new_linesLines00(xz119, xz120, xz121, xz1220, xz1230)
new_linesLines01(xz797, xz798, Char(Succ(xz79900)), xz800) → new_linesLines010(xz797, xz798, xz79900, xz800, xz798, xz79900)
new_lines(:(xz30, xz31)) → new_linesLines0(xz30, xz31, Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Zero))))))))))
new_linesLines012(xz887, xz888, xz889, xz890, xz905) → new_linesLines014(xz887, xz888, xz890)
new_linesLines011(xz797, xz798, :(xz8000, xz8001), xz815) → new_linesLines01(xz797, xz798, xz8000, xz8001)
new_linesLines010(xz887, xz888, xz889, xz890, Succ(xz8910), Succ(xz8920)) → new_linesLines010(xz887, xz888, xz889, xz890, xz8910, xz8920)
new_linesLines010(xz887, xz888, xz889, xz890, Zero, Succ(xz8920)) → new_linesLines013(xz887, xz888, xz889, xz890)
new_linesLines04(xz940, xz941, xz942, Char(Zero), xz944) → new_linesLines06(xz940, xz941, xz942, xz944, new_span2Ys1(xz942, xz944))
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Succ(xz9830), Zero) → new_linesLines07(xz978, xz979, xz980, xz981, xz982, new_span2Ys1(xz980, xz982))
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Zero, Zero) → new_lines(xz982)
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Succ(xz9830), Succ(xz9840)) → new_linesLines05(xz978, xz979, xz980, xz981, xz982, xz9830, xz9840)
new_linesLines02(xz119, :(xz1200, xz1201), xz127, xz121) → new_linesLines04(xz119, :(xz1200, xz1201), xz121, xz1200, xz1201)
new_linesLines01(xz797, xz798, Char(Zero), xz800) → new_linesLines011(xz797, xz798, xz800, new_span2Ys1(xz798, xz800))
new_linesLines03(xz119, xz120, xz121) → new_linesLines02(xz119, xz120, new_span2Ys1(xz121, xz120), xz121)
new_linesLines0(Char(Succ(xz900)), xz10, xz11) → new_linesLines00(xz900, xz10, xz11, xz11, xz900)
new_linesLines04(xz940, xz941, xz942, Char(Succ(xz94300)), xz944) → new_linesLines05(xz940, xz941, xz942, xz94300, xz944, xz942, xz94300)
new_linesLines09(xz940, xz941, xz942, :(xz9440, xz9441)) → new_linesLines04(xz940, xz941, xz942, xz9440, xz9441)
new_linesLines00(xz119, xz120, xz121, Zero, Zero) → new_lines(xz120)
new_linesLines010(xz887, xz888, xz889, xz890, Succ(xz8910), Zero) → new_linesLines012(xz887, xz888, xz889, xz890, new_span2Ys1(xz888, xz890))
new_linesLines014(xz797, xz798, :(xz8000, xz8001)) → new_linesLines01(xz797, xz798, xz8000, xz8001)
new_linesLines00(xz119, xz120, xz121, Zero, Succ(xz1230)) → new_linesLines03(xz119, xz120, xz121)
new_linesLines05(xz978, xz979, xz980, xz981, xz982, Zero, Succ(xz9840)) → new_linesLines08(xz978, xz979, xz980, xz981, xz982)
new_linesLines06(xz940, xz941, xz942, :(xz9440, xz9441), xz945) → new_linesLines04(xz940, xz941, xz942, xz9440, xz9441)
new_linesLines00(xz119, xz120, xz121, Succ(xz1220), Zero) → new_linesLines02(xz119, xz120, new_span2Ys1(xz121, xz120), xz121)
new_linesLines010(xz887, xz888, xz889, xz890, Zero, Zero) → new_lines(xz890)
The TRS R consists of the following rules:
new_span2Ys1(xz7, :(Char(Succ(xz6000)), xz61)) → new_span2Ys03(xz7, xz6000, xz61, xz7, xz6000)
new_span2Ys03(xz282, xz283, xz284, Succ(xz2850), Zero) → new_span2Ys01(xz282, xz283, xz284)
new_span2Ys03(xz282, xz283, xz284, Zero, Succ(xz2860)) → new_span2Ys01(xz282, xz283, xz284)
new_span2Ys03(xz282, xz283, xz284, Succ(xz2850), Succ(xz2860)) → new_span2Ys03(xz282, xz283, xz284, xz2850, xz2860)
new_span2Ys03(xz282, xz283, xz284, Zero, Zero) → []
new_span2Ys02(xz282, xz283, xz284, xz298) → :(Char(Succ(xz283)), xz298)
new_span2Ys1(xz7, :(Char(Zero), xz61)) → new_span2Ys04(xz7, xz61, new_span2Ys1(xz7, xz61))
new_span2Ys04(xz7, xz61, xz46) → :(Char(Zero), xz46)
new_span2Ys01(xz282, xz283, xz284) → new_span2Ys02(xz282, xz283, xz284, new_span2Ys1(xz282, xz284))
new_span2Ys1(xz7, []) → []
The set Q consists of the following terms:
new_span2Ys01(x0, x1, x2)
new_span2Ys03(x0, x1, x2, Zero, Zero)
new_span2Ys1(x0, :(Char(Succ(x1)), x2))
new_span2Ys02(x0, x1, x2, x3)
new_span2Ys03(x0, x1, x2, Succ(x3), Succ(x4))
new_span2Ys1(x0, [])
new_span2Ys03(x0, x1, x2, Zero, Succ(x3))
new_span2Ys04(x0, x1, x2)
new_span2Ys03(x0, x1, x2, Succ(x3), Zero)
new_span2Ys1(x0, :(Char(Zero), x1))
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_lines(:(xz30, xz31)) → new_linesLines0(xz30, xz31, Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Zero))))))))))
The graph contains the following edges 1 > 1, 1 > 2
- new_linesLines07(xz978, xz979, xz980, xz981, xz982, xz985) → new_linesLines09(xz978, xz979, xz980, xz982)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 5 >= 4
- new_linesLines05(xz978, xz979, xz980, xz981, xz982, Zero, Succ(xz9840)) → new_linesLines08(xz978, xz979, xz980, xz981, xz982)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5
- new_linesLines012(xz887, xz888, xz889, xz890, xz905) → new_linesLines014(xz887, xz888, xz890)
The graph contains the following edges 1 >= 1, 2 >= 2, 4 >= 3
- new_linesLines010(xz887, xz888, xz889, xz890, Zero, Succ(xz8920)) → new_linesLines013(xz887, xz888, xz889, xz890)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4
- new_linesLines09(xz940, xz941, xz942, :(xz9440, xz9441)) → new_linesLines04(xz940, xz941, xz942, xz9440, xz9441)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 4 > 5
- new_linesLines00(xz119, xz120, xz121, Succ(xz1220), Succ(xz1230)) → new_linesLines00(xz119, xz120, xz121, xz1220, xz1230)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 5 > 5
- new_linesLines0(Char(Succ(xz900)), xz10, xz11) → new_linesLines00(xz900, xz10, xz11, xz11, xz900)
The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3, 3 >= 4, 1 > 5
- new_linesLines00(xz119, xz120, xz121, Zero, Zero) → new_lines(xz120)
The graph contains the following edges 2 >= 1
- new_linesLines010(xz887, xz888, xz889, xz890, Zero, Zero) → new_lines(xz890)
The graph contains the following edges 4 >= 1
- new_linesLines0(Char(Zero), :(xz100, xz101), xz11) → new_linesLines01(:(xz100, xz101), xz11, xz100, xz101)
The graph contains the following edges 2 >= 1, 3 >= 2, 2 > 3, 2 > 4
- new_linesLines05(xz978, xz979, xz980, xz981, xz982, Zero, Zero) → new_lines(xz982)
The graph contains the following edges 5 >= 1
- new_linesLines010(xz887, xz888, xz889, xz890, Succ(xz8910), Zero) → new_linesLines012(xz887, xz888, xz889, xz890, new_span2Ys1(xz888, xz890))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4
- new_linesLines010(xz887, xz888, xz889, xz890, Succ(xz8910), Succ(xz8920)) → new_linesLines010(xz887, xz888, xz889, xz890, xz8910, xz8920)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 > 5, 6 > 6
- new_linesLines014(xz797, xz798, :(xz8000, xz8001)) → new_linesLines01(xz797, xz798, xz8000, xz8001)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3, 3 > 4
- new_linesLines011(xz797, xz798, :(xz8000, xz8001), xz815) → new_linesLines01(xz797, xz798, xz8000, xz8001)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3, 3 > 4
- new_linesLines013(xz887, xz888, xz889, xz890) → new_linesLines012(xz887, xz888, xz889, xz890, new_span2Ys1(xz888, xz890))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4
- new_linesLines01(xz797, xz798, Char(Zero), xz800) → new_linesLines011(xz797, xz798, xz800, new_span2Ys1(xz798, xz800))
The graph contains the following edges 1 >= 1, 2 >= 2, 4 >= 3
- new_linesLines01(xz797, xz798, Char(Succ(xz79900)), xz800) → new_linesLines010(xz797, xz798, xz79900, xz800, xz798, xz79900)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3, 4 >= 4, 2 >= 5, 3 > 6
- new_linesLines06(xz940, xz941, xz942, :(xz9440, xz9441), xz945) → new_linesLines04(xz940, xz941, xz942, xz9440, xz9441)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 4 > 5
- new_linesLines02(xz119, :(xz1200, xz1201), xz127, xz121) → new_linesLines04(xz119, :(xz1200, xz1201), xz121, xz1200, xz1201)
The graph contains the following edges 1 >= 1, 2 >= 2, 4 >= 3, 2 > 4, 2 > 5
- new_linesLines05(xz978, xz979, xz980, xz981, xz982, Succ(xz9830), Zero) → new_linesLines07(xz978, xz979, xz980, xz981, xz982, new_span2Ys1(xz980, xz982))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5
- new_linesLines08(xz978, xz979, xz980, xz981, xz982) → new_linesLines07(xz978, xz979, xz980, xz981, xz982, new_span2Ys1(xz980, xz982))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5
- new_linesLines05(xz978, xz979, xz980, xz981, xz982, Succ(xz9830), Succ(xz9840)) → new_linesLines05(xz978, xz979, xz980, xz981, xz982, xz9830, xz9840)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 > 6, 7 > 7
- new_linesLines04(xz940, xz941, xz942, Char(Succ(xz94300)), xz944) → new_linesLines05(xz940, xz941, xz942, xz94300, xz944, xz942, xz94300)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 5 >= 5, 3 >= 6, 4 > 7
- new_linesLines00(xz119, xz120, xz121, Succ(xz1220), Zero) → new_linesLines02(xz119, xz120, new_span2Ys1(xz121, xz120), xz121)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 4
- new_linesLines00(xz119, xz120, xz121, Zero, Succ(xz1230)) → new_linesLines03(xz119, xz120, xz121)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3
- new_linesLines04(xz940, xz941, xz942, Char(Zero), xz944) → new_linesLines06(xz940, xz941, xz942, xz944, new_span2Ys1(xz942, xz944))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 5 >= 4
- new_linesLines03(xz119, xz120, xz121) → new_linesLines02(xz119, xz120, new_span2Ys1(xz121, xz120), xz121)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 4